package main.leetcode.offer.firstround.from03to50;

import java.util.HashMap;

/**
 * 48.最长不含重复字符的子字符串
 *
 * <p>请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 *
 * <p>示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * <p>示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * <p>示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"
 * 是一个子序列，不是子串。
 *
 * <p>提示：s.length <= 40000
 */
public class ex48 {
    public static void main(String[] args) {
        System.out.println(new ex48().lengthOfLongestSubstring("au"));
    }

    // 滑动窗口
    //	public int lengthOfLongestSubstring(String s) {
    //		int n = s.length();
    //		if (n < 2) return n;
    //		HashMap<Character, Integer> count = new HashMap<>(n);
    //		int lo = 0, hi = 0, max = 0;
    //		char c;
    //		while (hi < n) {
    //			c = s.charAt(hi);
    //			if (count.containsKey(c)) // 例如abcdca
    //				lo = Math.max(count.get(c) + 1, lo); //  防止当hi遍历到最后一个a的时候lo跳回到第一个a+1（此时lo原本在d
    //			max = Math.max(max, hi - lo + 1);
    //			count.put(c, hi);
    //			hi++;
    //		}
    //		return max;
    //	}

    // 动态规划
    //    public int lengthOfLongestSubstring(String s) {
    //        int n = s.length();
    //        if (n < 2) return n;
    //        HashMap<Character, Integer> map = new HashMap<>(n);
    //        int[] dp = new int[n];
    //        dp[0] = 1;
    //        int max = 0;
    //        char c;
    //        map.put(s.charAt(0), 0);
    //        for (int i = 1; i < n; i++) {
    //            c = s.charAt(i);
    //            if (map.containsKey(c) && dp[i - 1] >= i - map.get(c)) { //
    // 上一个重复字符在dp[i-1]对应的字符串之中
    //                dp[i] = i - map.get(c);
    //            } else { // 未重复或在之前
    //                dp[i] = dp[i - 1] + 1;
    //            }
    //            map.put(c, i);
    //            max = Math.max(max, dp[i]);
    //        }
    //        return max;
    //    }

    // 动态规划 优化
    // 因为dp[i]只与dp[i-1]有关，所以可以将状态数组压缩成“滚动变量”
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n < 2) return n;
        HashMap<Character, Integer> map = new HashMap<>(n);
        int max = 0, pre = 1, curr; // pre相当于dp[i-1]，curr相当于dp[i]
        char c;
        map.put(s.charAt(0), 0);
        for (int i = 1; i < n; i++) {
            c = s.charAt(i);
            if (map.containsKey(c) && pre >= i - map.get(c)) { // 上一个重复字符在dp[i-1]对应的字符串之中
                curr = i - map.get(c);
            } else { // 未重复或在之前
                curr = pre + 1;
            }
            map.put(c, i);
            max = Math.max(max, curr);
            pre = curr; // 滚动
        }
        return max;
    }
}
